Obeleži sve kategorije koje odgovaraju problemu

Бинарна претрага преломне тачке

У свом најопштијем облику, бинарна претрага се може формулисати на следећи начин. Размотримо низ елемената такав да су елементи подељени у две групе, на основу неког својства \(P\). Елементи у почетном делу низа су сви такви да немају то својство \(P\), а елементи у завршном делу низа су сви такви да имају својство \(P\). Низ је, дакле, облика -----++++++++, где су са - означени елементи који немају, а са + елементи који имају својство \(P\). Могућа је и ситуација у којој је нека од група празна. Својство \(P\) може бити сасвим произвољно. На пример, у сортираном низу бројева можемо посматрати својство већи је или једнак \(X\) за неку дату вредност \(X\). Тада се у првом делу низа налазе елементи који нису већи или једнаки \(X\), тј. строго су мањи од \(X\), док се иза њих налазе елементи који имају својство, тј. већи су или једнаки \(X\). Даље, на пример, низ ученика може бити организован тако да су прво наведени дечаци, а затим девојчице.

Бинарна претрага нам може помоћи да ефикасно одредимо преломну тачку, тј. место где престаје једна и почиње друга група елемената. То може бити или позиција последњег елемента који нема својство \(P\) или првог елемента који има својство \(P\). Ако сви елементи низа имају својство \(P\), тада претрага за позицијом последњег елемента низа који нема својство треба да врати \(-1\). Ако ниједан елемент низа нема својство \(P\), тада претрага за позицијом првог елемента низа који има својство \(P\) треба да врати дужину низа. Познавање преломне тачке нам омогућава и да ефикасно одговоримо на питање колико је елемената у свакој групи (колико елемената низа нема, а колико елемената низа има својство \(P\)).

Класична бинарна претрага се лако формулише као претрага преломне тачке. Ако у низу пронађемо позицију првог елемента који је већи или једнак траженој вредности \(X\), тада можемо проверити да ли је та позиција унутар низа (строго мања од дужине низа) и да ли се на њој налази елемент \(X\) - ако је то испуњено елемент постоји у низу, а у супротном не постоји.

У наставку ће кроз низ задатака бити приказан алгоритам бинарне претраге преломне тачке у низу. У првим примерима у низу бројева ћемо тражити позицију првог елемента који је (строго или нестрого) већи или мањи од дате вредности, док ћемо у наредним примерима посматрати и другачије низове, подељене у односу на неко својство \(P\).

Позиција преломне тачке може бити пронађена и уз помоћ инвентивне употребе функција lower_bound и upper_bound.

Бинарна претрага преломне тачке

У свом најопштијем облику, бинарна претрага се може формулисати на следећи начин. Размотримо низ елемената такав да су елементи подељени у две групе, на основу неког својства \(P\). Елементи у почетном делу низа су сви такви да немају то својство \(P\), а елементи у завршном делу низа су сви такви да имају својство \(P\). Низ је, дакле, облика -----++++++++, где су са - означени елементи који немају, а са + елементи који имају својство \(P\). Могућа је и ситуација у којој је нека од група празна. Својство \(P\) може бити сасвим произвољно. На пример, у сортираном низу бројева можемо посматрати својство већи је или једнак \(X\) за неку дату вредност \(X\). Тада се у првом делу низа налазе елементи који нису већи или једнаки \(X\), тј. строго су мањи од \(X\), док се иза њих налазе елементи који имају својство, тј. већи су или једнаки \(X\). Даље, на пример, низ ученика може бити организован тако да су прво наведени дечаци, а затим девојчице.

Бинарна претрага нам може помоћи да ефикасно одредимо преломну тачку, тј. место где престаје једна и почиње друга група елемената. То може бити или позиција последњег елемента који нема својство \(P\) или првог елемента који има својство \(P\). Ако сви елементи низа имају својство \(P\), тада претрага за позицијом последњег елемента низа који нема својство треба да врати \(-1\). Ако ниједан елемент низа нема својство \(P\), тада претрага за позицијом првог елемента низа који има својство \(P\) треба да врати дужину низа. Познавање преломне тачке нам омогућава и да ефикасно одговоримо на питање колико је елемената у свакој групи (колико елемената низа нема, а колико елемената низа има својство \(P\)).

Класична бинарна претрага се лако формулише као претрага преломне тачке. Ако у низу пронађемо позицију првог елемента који је већи или једнак траженој вредности \(X\), тада можемо проверити да ли је та позиција унутар низа (строго мања од дужине низа) и да ли се на њој налази елемент \(X\) - ако је то испуњено елемент постоји у низу, а у супротном не постоји.

У наставку ће кроз низ задатака бити приказан алгоритам бинарне претраге преломне тачке у низу. У првим примерима у низу бројева ћемо тражити позицију првог елемента који је (строго или нестрого) већи или мањи од дате вредности, док ћемо у наредним примерима посматрати и другачије низове, подељене у односу на неко својство \(P\).